package leetcode每日一题;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 1. 问题描述
 *      查看数组是否有重复元素
 *
 * 2. 算法分析
 *      1. hashmap   时间和空间比较高  尤其当元素比较多的情况[,.....,1,....,1(非常靠后，之前没有重复元素)]
 *
 *      2. 位运算
 *          0 ^ a = a
 *          a ^ b = a ^ b
 *          a ^ a = 0
 *          由此我们可以知道设置一个初始变量 temp = 0
 *          temp ^= nums[i]
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 检查数组是否有重复元素 {
    public static void main(String[] args) {
        System.out.println(4 ^ 5 ^ 5);
    }

    public static boolean containsDuplicate1(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            if(map.containsKey(nums[i])) {
                return true;
            } else{
                map.put(nums[i],1);
            }
        }
        return false;
    }

    /**
     * 双指针  超出时间限制
     * @param nums
     * @return
     */
    public static boolean containsDuplicate2(int[] nums) {
        for(int i = 0; i < nums.length; i++) {
            for(int j = i+1; j < nums.length; j++) {
                if(nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 排序之后扫描即可  时间复杂度基于排序算法的策略
     * 直接调用jdk底层提供的排序算法即可  leetcode上的测试比较好
     * @param nums
     * @return
     */
    public static boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums); // 排序  O(nlogn)
        for(int i = 0; i < nums.length - 1; i++) {
            if(nums[i] == nums[i+1]) {
                return true;
            }
        }
        return false;
    }
}
